/**
 * 哈希表，通过后移解决冲突。设置墓碑thombstone解决删除后找不到后面的key的problem
 */

#include <stdlib.h>
#include "hash_table.h"

static void extendCapacity(HashTable* table);

void hashTableInit(HashTable* table, HashFn hash, CompareFn compare) {
    table->capacity = 0;
    table->size = 0;
    table->data = NULL;
    table->hash = hash;
    table->compare = compare;
}

Entry* hashTablePut(HashTable* table, void* key, void* val) {
    if(table->size >= table->capacity * HASH_TABLE_EXTEND_THRETHOLD) {
        extendCapacity(table);
    }
    Entry* entry = hashTableGetEntry(table, key);
    entry->key = key;
    entry->val = val;
    table->size++;
    return entry;
}

Entry hashTableRemove(HashTable* table, void* key) {
    Entry* entry = hashTableGetEntry(table, key);
    Entry res;
    res.key = entry->key;
    res.val = entry->val;
    entry->key = NULL;
    entry->val = HASH_TABLE_TOMBSTONE_VAL;
    return res;
}

void* hashTableGet(HashTable* table, void* key) {
    return hashTableGetEntry(table, key)->val;
}

Entry* hashTableGetEntry(HashTable* table, void* key) {
    if(table->capacity == 0) return NULL;
    int index = table->hash(key) & (table->capacity - 1);
    // printf("hashTableGetEntry hash: %d, capacity: %d, size: %d\n", 
        // index, table->capacity, table->size);
    Entry* thombstone = NULL;
    for(;;) {
        Entry* entry = table->data + index;
        if(entry->key == NULL) {
            if(entry->val == NULL) {
                return thombstone == NULL ? entry : thombstone;
            } else {
                // 继续扫描
                thombstone = entry;
            }
        } else if(table->compare(key, entry->key) == 0) {
            return entry;
        }
        index = (index + 1) & (table->capacity - 1);
    }
}

static void extendCapacity(HashTable* table) {
    int newCapacity = table->capacity == 0 ? HASH_TABLE_DEFAULT_CAPACITY : table->capacity * 2;
    Entry* data = calloc(newCapacity, sizeof(Entry));
    // printf("extendCapacity start\n");
    Entry* oldData = table->data;
    table->data = data;
    for (size_t i = 0; i < table->capacity; i++)
    {
        Entry* entry = oldData + i;
        if(entry->key == NULL) continue;
        Entry* dest = hashTableGetEntry(table, entry->key);
        dest->key = entry->key;
        dest->val = entry->val;
    }
    free(oldData);
    table->capacity = newCapacity;
    // printf("extendCapacity end\n");
}
